package sort.quickort;

/**
 * 快速排序
 */
public class QuickSort {

    public static void main(String[] args) {

        int[] nums = new int[1000000];
        long start = System.currentTimeMillis();
        for (int k = 0; k < 10; k++) {
            for (int j = 0; j < nums.length; j++) {
                nums[j] = (int) (Math.random() * 1000);
            }
            quickSort(nums);
        }
        System.out.println("quick sort cost ：" + (System.currentTimeMillis() - start));
    }

    public static void quickSort(int[] nums) {

        if (nums == null || nums.length == 0) {
            return;
        }
        qSort(nums, 0, nums.length - 1);

//        for(int i =0;i<nums.length;i++) {
//            System.out.println(nums[i]);
//        }
    }

    private static void qSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        //获取第一个数据（排序区分左右两部分数据：左边小于，右边大于该数）
        int pivot = nums[start];
        int left = start;
        int right = end;
        while (left <= right) {
            while (left <= right && nums[left] < pivot) {
                left++;
            }
            while (left <= right && nums[right] > pivot) {
                right--;
            }
            if (left <= right) {
                int tmp = nums[right];
                nums[right] = nums[left];
                nums[left] = tmp;
                left++;
                right--;
            }
        }
        //想象图形（移动过程） 递归左排、右排
        qSort(nums, start, right);     //为什么是right，left加了1之后，大于right
        qSort(nums, left, end);
    }
}
